﻿// 0816train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 给你一个整数数组 nums ，数组中的元素 互不相同
 返回该数组所有可能的子集（幂集）
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 */

class Solution01 {
public:
    vector<vector<int>> subsets(vector<int>& nums)
	{
        vector<vector<int>>result;
        vector<int>subnums;
        backTrack(0, subnums, nums, result);
        return result;
        //subsets------
    }

    void backTrack(int i, vector<int>&subnums, vector<int>&nums, vector<vector<int>>&result)
    {
        //加入子集
        result.push_back(subnums);

        //递归终止条件
        if (i >= nums.size()) return;

        for (int j=i; j<nums.size(); j++)
        {
            subnums.push_back(nums[j]);
            backTrack(j + 1, subnums, nums, result);
            subnums.pop_back();
        }

        //backTrack
    }

    //Solution01
};


/*
 示例1
 输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
 */

class Solution02 {
public:
    int result = 0;
    int findTargetSumWays(vector<int>& nums, int target)
	{

        backTrack(0, target, nums);
        return result;
    }

    void backTrack(int i, int remain, vector<int>&nums)
    {
        //递归终止条件
        if (i>=nums.size())
        {
            if (remain == 0)
            {
                result += 1;
            }
            return;
        }

        //nums[i]取负数
        remain += nums[i];
        backTrack(i + 1, remain, nums);
        remain -= nums[i];

        //nums[i]取正数
        remain -= nums[i];
        backTrack(i + 1, remain, nums);
        remain += nums[i];
    }

};

/*
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

 */

class Solution03 {
public:
    vector<vector<int>>result_vec;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        vector<int>subnums;
        backTrack(0, subnums, nums);
        return result_vec;
    }

    void backTrack(int i, vector<int>&subnums, vector<int>&nums)
    {
        result_vec.push_back(subnums);

        //递归终止条件
        if (i>=nums.size())
        {
            return;
        }

        for (int j=i; j<nums.size(); j++)
        {
            if (j > i && nums[j] == nums[j - 1]) continue;

            subnums.push_back(nums[j]);
            backTrack(j + 1, subnums, nums);
            subnums.pop_back();
        }

    }
};

/*
 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
class Solution04 {
public:
    vector<vector<int>>result;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int>track;
        vector<bool>used(nums.size(), false);
        backTrack(track, used, nums);
        return result;
    }

    void backTrack(vector<int>&track,vector<bool>&used, vector<int>& nums)
    {
        if (track.size()==nums.size())
        {
            result.push_back(track);
            return;
        }

        for (int i=0; i<nums.size(); i++)
        {
            if (used[i]) continue;

            track.push_back(nums[i]);
            used[i] = true;
            backTrack(track, used, nums);
            track.pop_back();
            used[i] = false;

        }

    }
};


int main()
{
	{
        //nums = [1,2,3]
        vector<int>nums = { 1,2,3 };
        Solution04 solu;
        vector<vector<int>>result = solu.permute(nums);
        cout << result.size();
        return 0;
	}


	{
        //nums = [1,2,2]
        vector<int>nums = { 1,2,2 };
        Solution03 solu;
        vector<vector<int>>result = solu.subsetsWithDup(nums);

        for (auto&vec:result)
        {
            for (auto&num:vec)
            {
                cout << num << ' ';
            }
            cout << '\n';
        }

        return 0;
	}
	{
        //nums = [1,1,1,1,1], target = 3
        vector<int>nums = { 1,1,1,1,1 };
        int target = 3;
        Solution02 solu;
        cout << solu.findTargetSumWays(nums, target);
        return 0;

	}
    //输入：nums = [0, 1, 2]
    vector<int>nums = { 0,1,2 };
    Solution01 solu;
    vector<vector<int>>result = solu.subsets(nums);

    for (auto&mini_vec:result)
    {
        for (auto&num:mini_vec)
        {
            cout << num << ' ';
        }
        cout << '\n';
    }

    //main-------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
